#include<vector>
using namespace std;
class Solution {
public:
    int maxSumAfterPartitioning(vector<int>& A, int K) {
        int n = A.size();
        if (n < 1) return 0;
        vector<int> dp(n, INT32_MIN);
        dp[0] = A[0];
        for (int i = 1; i < n; ++i) {
            int max = INT32_MIN;
            for (int j = 1; j <=K&&i-j+1>=0;++j) {
                max = max > A[i - j + 1] ? max : A[i - j + 1];
                int tmp= max * j;
                if (i - j >= 0)
                    tmp+=dp[i - j];
                dp[i] = dp[i] > tmp ? dp[i] : tmp;
            }
        }
        return dp[n - 1];
    }
};